package com.gxc.array;

/**
 * 最长递增子序列问题
 * eg:[3,1,2,6,3,4] ->  [1,2,3,4]
 *  子序列：不连续
 * 解法：
 * a)
 * 尝试已i位置为结束的最长递增子序列，
 * i+1的值如果比i大，则i位置的最大递增子序列长度+1；
 * 否则，找i之前比i+1值小的位置j, j位置的最大递增子序列长度+1
 * b)
 * 建立一个辅助数据ends，数组内存的数据是目前已知所有的最大递增子序列的尾数最小值构成的有序数组
 * https://blog.csdn.net/zhizhengguan/article/details/124714546
 * 例如
 * [10,9,2,5,3,7,101,4,1,********* ,i,********]
 * 10
 * 9
 * 2 5 7 101
 * 2 3 7 101
 * 2 3 4
 * 1
 * ends = [1,3,4,101]
 * 当i大于ends 数组中任意值 j ，一定可以构成递增序列
 * end[j]结尾的子序列 + i
 */
public class LongestIncreasingSubsequence {

    public static void main(String[] args) {
        int[] random = new int[]{3,1,2,3,5,6,3,4};
        System.out.println(process(random));
        System.out.println(process2(random));
    }

    /**
     * 暴力递归  ,每个位置为结束的最长递增子序列
     * @param arr
     * @return
     */
    public static int process(int[] arr) {
        if (arr == null || arr.length==0) return 0;

        int[] help = new int[arr.length];
        help[0] = 1;
        int max = 1;
        for (int i = 1; i < arr.length; i++) {
            int num = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    num = Math.max(help[j] +1, num);
                }
            }
            max = Math.max(max, num);
            help[i] = num;
        }
        return max;
    }

    /**
     * 建立一个辅助数据ends，数组内存的数据是目前已知所有的最大递增子序列的尾数最小值构成的有序数组
     * @param arr
     * @return
     */
    public static int process2(int[] arr) {
        if (arr == null || arr.length==0) return 0;

        int[] ends = new int[arr.length];
        int pos = 0;
        ends[0] = arr[0];

        int loc = 0;
        for (int i = 1; i < arr.length; i++) {
            //查找比 target 大的最小值
            loc = dichotomy(ends, arr[i], pos);
            //ends最大值都比当前值小。则扩大ends数组
            if (loc == -1) {
                ends[++pos] = arr[i];
            } else {
                ends[loc] = arr[i];
            }
        }
        return pos+1;
    }

    /**
     * 二分法查找,查找比 target 大的最小值
     * @param arr
     * @param target
     * @param pos
     * @return
     */
    public static int dichotomy(int[] arr, int target, int pos) {
        if (target>arr[pos]) return -1;

        int l = 0;
        int r = pos;

        int mid = 0;
        while (l<=r) {
            //避免溢出
            mid = l + (r-l)/2;
            if (arr[mid] == target) return mid;
            else if (arr[mid] > target) {
                r = mid-1;
            } else {
                l = mid+1;
            }
        }
        return l;
    }

}
